package 第二周;

/**
 * @author xhw
 * @date 2024/3/18
 */

public class 最长回文子串 {
    //给你一个字符串 s，找到 s 中最长回文
    //子串
    //。
    //
    //如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
    //
    //
    //
    //示例 1：
    //
    //输入：s = "babad"
    //输出："bab"
    //解释："aba" 同样是符合题意的答案。
    //示例 2：
    //
    //输入：s = "cbbd"
    //输出："bb"
    //
    //
    //提示：
    //
    //1 <= s.length <= 1000
    //s 仅由数字和英文字母组成
        public static void main(String[] args) {
            System.out.println(longestPalindrome("babad"));
            System.out.println(longestPalindrome("cbbd"));
        }

        private static String longestPalindrome(String s) {
            if (s == null || s.length() < 1) {
                return "";
            }

            int start = 0; // 起始位置
            int end = 0;   // 结束位置

            for (int i = 0; i < s.length(); i++) {
                // 奇数长度的回文串中心点
                int len1 = expandAroundCenter(s, i, i);
                // 偶数长度的回文串中心点
                int len2 = expandAroundCenter(s, i, i + 1);
                // 找到最长的那个
                int len = Math.max(len1, len2);
                // 更新答案
                if (len > end - start) {
                    start = i - (len - 1) / 2;
                    end = i + len / 2;
                }
            }

            return s.substring(start, end + 1);
        }

        private static int expandAroundCenter(String s, int L, int R) {
            while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
                L--;
                R++;
            }
            return R - L - 1;
        }
    }